package leetcode_day._2021._202106._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/6 21:40
 * 一和零
 * 算法：动态规划
 */
public class _06_474 {

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s : strs) {
            int[] count = count(s);
            for (int i = m; i >= count[0]; i--) {
                for (int j = n; j >= count[1]; j--)
                    dp[i][j] = Math.max(dp[i][j], dp[i - count[0]][j - count[1]] + 1);
            }
        }
        return dp[m][n];
    }
    public int[] count(String s) {
        int[] res = new int[2];
        for (char c : s.toCharArray()) {
            if ('0' == c) ++res[0];
            else ++res[1];
        }
        return res;
    }

}
